using System.Collections.Generic;

// 二叉树最小深度搜索算法
public class SearchMinDepth
{

    /// <summary>
    /// 使用广度优先 BFS比较快速找到最小深度 因为找到叶子节点就撤即可
    /// </summary>
    /// <param name="root"></param>
    /// <returns></returns>
    public int MinDepth(TreeNode root) {
        int minDepth = 1;
        if(root == null) return 0;
        Queue<TreeNode> queue = new();
        queue.Enqueue(root);
        while(queue.Count > 0){
            int size = queue.Count;
            for(int i = 0; i < size; i++){
                TreeNode curNode = queue.Dequeue();
                if(curNode.left == null && curNode.right == null) return minDepth;
                if(curNode.left != null) queue.Enqueue(curNode.left);
                if(curNode.right != null) queue.Enqueue(curNode.right);
            }
            minDepth++;
        }
        return minDepth;
    }
}
